Greatest Common Divisor From Factorisation

Theorem

Given integers \(a = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \dots \cdot p_n^{\alpha_n}\) and \(b = p_1^{\beta_1} \cdot p_2^{\beta_2} \cdot \dots \cdot p_n^{\beta_n}\) written in their prime factorisations, the greatest common divisor of \(a\) and \(b\) is given by

\[ \gcd(a, b) = p_1^{\min\{\alpha_1, \beta_1\}} \cdot p_2^{\min\{\alpha_2, \beta_2\}} \dots \cdot p_n^{\min\{\alpha_n, \beta_n\}}.\]

Note that as written above, we use the same set of primes in the factorisation for each \(a\) and \(b\). This is just for notational simplicity. Think of \(\{p_1, \dots, p_n\}\) as the set of all primes which divide either \(a\) or \(b\), and the powers \(\alpha_i\) or \(\beta_i\) may be \(0\) as necessary.

The idea here is very simple, choosing a power bigger than either \(\alpha_i\) or \(\beta_i\) for \(p_i\) will result in the result not being a common divisor, however choosing anything smaller than both will not be as big as it can be. Hence we take the minimimum of the corresponding powers.

Proof

This follows from the expression of divisors from the unique factorisation.

That is, some integer \(m\) is a divisor of \(a\) and \(b\) if

\[ m = p_1^{\gamma_1} \cdot p_2^{\gamma_2} \cdot \dots \cdot p_n^{\gamma_n}\]

where \(0 \leq \gamma_i \leq \alpha_i, \beta_i\) for all \(i \in \{1, \dots, n\}\). Since \(p_i \geq 2\) for each \(p_i\), maximising powers of each \(p_i\) results in the greatest integer \(m\). As such, to maintain the condition above, we choose \(\gamma_i = \min\{\alpha_i, \beta_i\}\) for each \(i\).

Example

The greatest common divisor of \(a = 8624 = 2^4 \times 7^2 \times 11\) and \(b = 415030 = 2 \times 5 \times 7^3 \times 11^2\) is

\[ 2 \times 7^2 \times 11.\]